//
// Description: 快速幂运算模板
// Created by Loading on 2021/6/26.
//

/* 用于：求 x^index % MOD */
/* 时间复杂度 O(log index)，一般幂运算为 O(index) */

// 例题：5802. 统计好数字的数目

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

constexpr int MOD = 1e9 + 7;

uLL fast_power(int x, int index) {
    uLL res = 1, base = x;
    /* 将 index 指数转为二进制，遍历二进制序列，为 1 的时候对结果进行累乘 */
    /* 示例：2^11 ，11 的二进制形式为 1011，结果为：2^8 * 2^3 * 2^0 */
    while (index) {
        if (index & 0x01) {
            res = res * base % MOD;
        }
        base = base * base % MOD;
        index >>= 1;
    }

    return res;
}

int main() {
    uLL fast_power_res = fast_power(2, 63);
    cout << "快速幂运算：" << fast_power_res << endl;
}